---
title: "拯救oibh总部"
created: 2025-11-28
tags:
  - 算法
---

# 拯救oibh总部

## 题目 [拯救oibh总部](https://www.luogu.com.cn/problem/P1506)

![[image-3cda9c6e.png]]

## 思路分析

主要是怎么处理这个读入

一个比较棘手的问题 如果读入的数据是没空格的 我们前面的经验是说使用字符数组存 然后用`for(int i=0;i<n;i++) cin>>g[i]`读入
但是字符数组不会自动补0 会变成这个样子

![[image-99f47904.png]]

一种解决方法是 仍旧用字符数组读 然后手动加一圈

```cpp
char g[N][N];
    for(int i=1;i<=n;i++)
        cin>>g[i]+1;

     for(int i=0;i<=n+1;i++) {
        g[i][0]=g[i][m+1]='0'; // 填充左右边界
    }
    for(int j=0;j<=m+1;j++) {
        g[0][j] = g[n+1][j]='0'; // 填充上下边界
    }
```

或者改成int数组

```cpp
int g[N][N];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;cin>>s;
            if(s=='0')
                g[i][j]=0;
            else
                g[i][j]=1;
        }
    }
```

```cpp
int g[N][N];

    for(int i=1;i<=n;i++){
        string line;
        cin>>line;
        for(int j=1;j<=m;j++){
            g[i][j]=line[j-1]-'0';
        }
    }
```

要注意的是 换了int数组后 涉及判断的地方都得改成用0 而不是'0'

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=510;

char g[N][N];

bool st[N][N];

int n,m;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]=='0'){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++)

		cin>>g[i]+1;

 	for(int i=0;i<=n+1;i++) {

        g[i][0]=g[i][m+1]='0'; // 填充左右边界

    }

    for(int j=0;j<=m+1;j++) {

        g[0][j] = g[n+1][j]='0'; // 填充上下边界

    }

//	for(int i=0;i<=n+1;i++){

//		for(int j=0;j<=m+1;j++)

//			cout<<g[i][j]<<" ";

//		cout<<endl;

//	}

	bfs(0,0);

	int cnt=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(g[i][j]=='0' && !st[i][j]){

				cnt++;

			}

		}

	}

	cout<<cnt;

	return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=510;

int g[N][N];

bool st[N][N];

int n,m;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			char s;cin>>s;

			if(s=='0')

				g[i][j]=0;

			else

				g[i][j]=1;

		}

	}

//	for(int i=0;i<=n+1;i++){

//		for(int j=0;j<=m+1;j++)

//			cout<<g[i][j]<<" ";

//		cout<<endl;

//	}

//

	bfs(0,0);

	int cnt=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(g[i][j]==0 && !st[i][j]){

				cnt++;

			}

		}

	}

	cout<<cnt;

	return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=510;

int g[N][N];

bool st[N][N];

int n,m;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n+1 && y>=0 && y<=m+1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(q.size()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				st[nx][ny]=true;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		string line;

		cin>>line;

		for(int j=1;j<=m;j++){

			g[i][j]=line[j-1]-'0';

		}

	}

//	for(int i=0;i<=n+1;i++){

//		for(int j=0;j<=m+1;j++)

//			cout<<g[i][j]<<" ";

//		cout<<endl;

//	}

//

	bfs(0,0);

	int cnt=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(g[i][j]==0 && !st[i][j]){

				cnt++;

			}

		}

	}

	cout<<cnt;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[填涂颜色|填涂颜色]] 🏠 [[00-刷题理模型]] ➡️ [[染色问题|染色问题]]